/*----------------------------------------------------------------
 *  Author:        Siedin Evgen
 *  Written:       24/2/2013
 *  Last updated:  24/2/2013
 *
 *    
 *  Deque API
 *
 *----------------------------------------------------------------*/

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Deque<Item> implements Iterable<Item>
{
   private Node first, last;

   private int size;

   private class Node
   {
      private Item item;

      private Node next;

      private Node prev;
   }

   public Deque()
   {
      size = 0;
   }

   public boolean isEmpty()
   {
      return size == 0;
   }

   public int size()
   {
      return size;
   }

   public void addFirst(Item item)
   {
      if (item == null)
      {
         throw new NullPointerException();
      }

      Node oldFirst = first;
      first = new Node();
      first.item = item;
      first.next = oldFirst;

      if (isEmpty())
      {
         last = first;
      }
      else
      {
         oldFirst.prev = first;
      }

      size++;
   }

   public void addLast(Item item)
   {
      if (item == null)
      {
         throw new NullPointerException();
      }

      Node oldLast = last;
      last = new Node();
      last.item = item;
      last.next = null;
      if (oldLast != null)
      {
         oldLast.next = last;
      }
      last.prev = oldLast;
      if (isEmpty())
      {
         first = last;
      }

      size++;
   }

   public Item removeFirst()
   {
      if (isEmpty())
      {
         throw new NoSuchElementException();
      }

      size--;
      Node oldFirst = first;
      first = first.next;

      if (first != null)
      {
         first.prev = null;
      }
      else
      {
         last = null;
      }



      return oldFirst.item;
   }

   public Item removeLast()
   {
      if (isEmpty())
      {
         throw new NoSuchElementException();
      }

      size--;
      Node oldLast = last;
      last = last.prev;
      if (last != null)
      {
         last.next = null;
      }
      else
      {
         first = null;
      }
      return oldLast.item;
   }

   public Iterator<Item> iterator()
   {
      return new DequeIterator();
   }

   private class DequeIterator implements Iterator<Item>
   {
      private Node current = first;

      public boolean hasNext()
      {
         return current != null;
      }

      public Item next()
      {
         if (current == null)
         {
            throw new NoSuchElementException();
         }

         Item item = current.item;
         current = current.next;
         return item;
      }

      public void remove()
      {
         throw new UnsupportedOperationException();
      }
   }
}
